7.6 Error Correction

89

Fig. 7.3 Input–output

relationships for a device

such as an electromechanical

relay (solid line) and a

field-effect transistor (dashed

line)

It is perfectly possible to devise codes that can detect and correct errors. Hamming

defines systematic codes as those in which each code symbol has exactly nn binary

digits,mm being associated with the information being conveyed andk equals n minus mk = n −m being

used for error detection and correction. The redundancy (cf. Eq. 6.18) of a systematic

code (subscript s.c.) is defined as

upper R Subscript s period c period Baseline equals n divided by m periodRs.c. = n/m .

(7.22)

Hamming (1950) constructed a single error-detecting code as follows: Information

is placed in the first n minus 1n −1 positions of nn binary digits. Either a 0 or a 1 is placed

in the nnth position, the choice being made to ensure an even number of 1s in the nn

digit word. A single (or odd number of) error would leave an odd number of 1s in

the word. Clearly, the redundancy is n divided by left parenthesis n minus 1 right parenthesisn/(n −1). This type of error-detecting code is

called a parity check; this particular one is an even parity check. nn should be small

enough such that the probability of more than one error is negligible.

To make an error-correcting code, a larger number (k greater than 1k > 1) of positions is given to

parity checking and filled with values appropriate to selected information positions.

When the message is received,kk checks are applied in order, and if the observed value

agrees with the previously calculated value, one writes a 0, but a 1 if it disagrees, in a

new number called the checking number, which must give the position of any single

error—i.e., it must describe m plus k plus 1m + k + 1 different things—hence, kk must satisfy

m plus k plus 1 less than or equals 2 Superscript k Baseline less than or equals 2 Superscript n Baseline divided by left parenthesis n plus 1 right parenthesis periodm + k + 1 ≤2^k ≤2ⁿ/(n + 1) .

(7.23)

The principle can obviously be extended to double error-correcting codes, which, of

course, further increase the redundancy. ¹²

12 See also Levenshtein (2001) on the problem of efficient reconstruction of an unknown sequence

from versions distorted by noise.